This invention relates generally to data encoding in solid-state storage devices. Methods and apparatus are provided for encoding data for storage in multilevel solid-state memory, together with data storage devices incorporating same.
In solid-state memory such as flash memory and phase-change memory, the fundamental storage unit (the “cell”) can be set to q different states, or “levels”, permitting storage of information. Each cell can be used to store a qary symbol with each of the q possible symbol values being represented by a different cell level. In so-called “multilevel” memory, the memory cells can be set to q>2 cell levels, permitting storage of more than one bit per cell.
Detection of data stored in multilevel memory cells relies on identifying the q different cell levels on readback. In flash and phase change memory (PCM), for example, the different cell levels exhibit different electrical charge and electrical resistance characteristics respectively, and these can be detected via current or voltage measurements on the cells. On readout of cells, the read signal level can be compared with a set of reference signal levels indicative of the q cell levels in order to determine which level each cell is set to and thus detect the stored symbol value. A basic problem here is that the physical quantity measured during cell readout is subject to variability, e.g. due to noise and/or drift in measured values with time or cell usage. Multiple read operations on cells set to any given cell level will therefore yield a distribution of read signal levels.
Accurate characterization of the level distributions on readback of multilevel-cell (MLC) memory is crucial to readback performance. Currently the more sophisticated read detection systems use self-adaptive techniques in which the readback signals from a block of memory cells are processed to estimate statistics for the q cell levels, and these level statistics are then used for detection of data in that block of cells. Such self-adaptive techniques are particularly useful where the level statistics are not stationary in time and cannot be determined a priori by characterization, e.g. due to drift effects mentioned above. As readback block sizes decrease, however, it becomes more difficult to obtain reliable estimates of the level statistics. Current PCM applications, for example, use a readback block size of 64 bits, which corresponds to 32 (q=4)-level cells, and further reduction in block size can be envisaged. When reading and writing such small blocks of data, it is possible that one or more of the q cell levels is only written a few times, or even not at all. Such data asymmetry can make it very difficult to estimate level statistics, resulting in poor error-rates on readback.
In view of the above, it is desirable to program all MLC levels as many times as possible. Prior solutions to this type of problem propose encoding the input data using balanced codes. In the codewords for balanced codes, all of the q symbol values appear with equal multiplicities (number of occurrences). This ensures that each cell level is written the same number of times, and thus appears the maximum number of times on readback. For example, “Coding Schemes for Multi-Level Channels with Unknown Gain and/or Offset”, Immink, Proc. IEEE Intern. Symp. on Information Theory, 2013, pp. 709-713, proposes codes in which all codewords have equal balance and energy. Schemes for achieving balanced binary sequences via a bit-flipping approach are disclosed in “Balancing sets of vectors,” Alon et al., IT-34, January 1988, pp. 128-1301. Here, two bit-flipping algorithms are proposed for binary length-n sequences that have either 1 bit or log2(n) bit redundancy. “Balanced modulation for nonvolatile memories”, H. Zhou, A. Jiang, http://arxiv.org/abs/1209.0744, September 2012, discloses use of a bit-flipping algorithm to achieve balanced binary sequences, permitting level estimation in non-volatile memories by adjusting level thresholds on readback to balance the readback words. A recursive bit-flipping approach is disclosed for MLC memory and requires significant redundancy, with consequent code rate penalty.